3499. Summing subsets

Let G(S) denote the sum of the elements of a set S, and let F(n) be the sum of all values G(S) over all subsets of the set consisting of the first n positive integers. For example,

F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24

For a given integer n, find the value of the sum F(1) + F(2) + … + F(n).

Input. The first line contains the number of test cases t (t ≤ 1000). Each of the following t lines contains one integer n (1 ≤ n ≤ 10⁹).

Output. Print t lines – one number per line for each corresponding test case. Since the answers may be very large, print them modulo 8388608.

Sample input	Sample output
3 1 2 3	1 7 31

SOLUTION

combinatorics

Algorithm analysis

Let us find a formula for F(n).

Theorem. Each element i appears in exactly half of all subsets, that is, in 2^{n – 1} subsets.

Proof. The total number of all subsets (including the empty set) of the set {1, 2, …, n} is 2ⁿ. Fix some element i. Any subset that contains i can be uniquely specified by choosing a subset of the remaining n – 1 elements. Therefore, the number of subsets containing i is equal to the total number of subsets of a set of size n – 1, that is, 2^n-1. But 2^n-1 is exactly half of 2ⁿ. Hence, each element i appears in exactly half of all subsets.

Therefore:

F(n) = = = 2^{n – 2} * n (n + 1)

We need to compute the following sum:

= =

=

It remains to evaluate the given sum.

Let us consider a finite geometric series (including the zero term):

Differentiate both sides with respect to r:

Multiply both sides by r:

Substitute r = 2. Note that the term with k = 0 equals zero.

=

= (n – 1) * 2^{n + 1} + 2

Thus, we obtain the formula:

= (n – 1) * 2^{n + 1} + 2

Similarly, we can derive the following formula:

= (n² – 2n + 3) * 2^{n + 1} – 6

Substitute them into the expression:

= ((n² – 2n + 3) * 2^{n + 1} – 6) + ((n – 1) * 2^{n + 1} + 2) =

2^{n + 1} (n² – n + 2) – 4

Therefore:

= (2^{n + 1} (n² – n + 2) – 4) = 2^{n – 1} (n² – n + 2) – 1

Example

Let us compute several values of the function F(n):

F(1) = (1) = 1,

F(2) = (1) + (2) + (1 + 2) = 6,

F(3) = (1) + (2) + (3) + (1 + 2) + (1 + 3) + (2 + 3) + (1 + 2 + 3) = 24

Thus,

F(1) = 1,

F(1) + F(2) = 1 + 6 = 7,

F(1) + F(2) + F(3) = 1 + 6 + 24 = 31

Now, let us compute these same sums using the formula:

F(1) = 2^{1 – 1} (1² – 1 + 2) – 1 = 1,

F(1) + F(2) = 2^{2 – 1} (2² – 2 + 2) – 1 = 7,

F(1) + F(2) + F(3) = 2^{3 – 1} (3² – 3 + 2) – 1 = 31

Algorithm implementation

Declare a constant for the modulus.

#define MOD 8388608 // 2^23

The PowMod function computes the value of xⁿ mod m.

long long PowMod(long long x, long long n, long long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);

return (x * PowMod(x, n - 1, m)) % m;

}

The main part of the program. Read the numbere of test cases tests.

scanf("%d", &tests);

while (tests--)

{

Read the input value n.

scanf("%lld", &n);

Compute the answer using the formula.

res = PowMod(2, n - 1, MOD); // 2^(n-1) mod MOD

t = ((n % MOD) * (n % MOD)) % MOD; // n^2

t = (t - n + MOD + 2) % MOD; // n^2 - n + 2

res = (res * t - 1 + MOD) % MOD;

Print the answer.

printf("%lld\n", res);

}